from typing import List


class Solution:
    def videoStitching(self, clips: List[List[int]], time: int) -> int:
        clips.sort()
        inf = float('inf')
        n = len(clips)
        dp = [inf for _ in range(time + 1)]
        dp[0] = 0
        for i in range(n):
            start, end = clips[i]
            start = min(start, time)
            end = min(end, time)
            for j in range(start, end + 1):
                if j > time: break
                dp[end] = min(dp[end], dp[j] + 1)

        return dp[-1] if dp[-1] != inf else -1


if __name__ == '__main__':
    s = Solution()
    r = s.videoStitching([[0, 2], [4, 6], [8, 10], [1, 9], [1, 5], [5, 9]], time=10)
    print(r)
